package demo.practice.dp;

public class P361 {

    /**
     * W 墙壁
     * E 敌人
     * 0 标识空行
     *
     * @param grid
     * @return
     */


    public int maxKilledEnemies(char[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int h = grid.length, w = grid[0].length;

        int[][] dp = new int[h][w];


        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dp[i][j] = 0;
                if (grid[i][j] == 'W') {
                    continue;
                }
                if (grid[i][j] == 'E') {
                    dp[i][j] += 1;
                }

                if (i > 0) {
                    dp[i][j] += dp[i - 1][j];
                }

                if (j > 0) {
                    dp[i][j - 1] += dp[i][j - 1];
                }
            }
        }


        int max = 0;
        for (int i = h - 1; i >= 0; i--) {
            for (int j = w - 1; j >= 0; j--) {
                if (grid[i][j] == 'W') {
                    continue;
                }
                if (i < h - 1) {
                    dp[i][j] += dp[i + 1][j];
                }

                if (j < h - 1) {
                    dp[i][j] += dp[i][j + 1];
                }

                if(grid[i][j]!= 'E' ){
                    max= Math.max(dp[i][j],max );
                }
            }
        }
        return max;
    }
}
